package learn.heap;

import learn.CommUtil;
import learn.link.Node;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最大线段重合问题;
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 */
public class CoverMax {

    public static void main(String[] args) {
        Line l1 = new Line(1, 4);
        Line l2 = new Line(2, 4);
        Line l3 = new Line(3, 7);
        Line l4 = new Line(4, 9);
        Line l5 = new Line(9, 10);

        Line[] lines = {l1, l2, l3, l4, l5};

        System.out.println(process(lines));

    }

    /**
     * 1.线段的重合数就是穿过一天线段起点的线段数
     * 时间复杂度O[n*logn]
     * 空间复杂度 O[n]
     * @param lines
     * @return
     */
    public static int process(Line[] lines) {
        //升序
        Arrays.sort(lines, (l1, l2) -> l1.start - l2.start);

        //遍历数组,统计穿过各个点的数量
        PriorityQueue<Line> heap = new PriorityQueue<>((l1, l2) -> l1.end - l2.end);
        heap.size();
        int max = 0;
        for (int i = 0; i < lines.length; i++) {
            while (!heap.isEmpty() && heap.peek().end <= lines[i].start) {
                heap.poll();
            }
            heap.add(lines[i]);
            max = Math.max(heap.size(), max);
            System.out.println(lines[i].start + "-" + lines[i].end + " : " + heap.size());
        }
        return max;
    }

    ;

    public static class Line {
        public int start;
        public int end;

        public Line(int s, int e) {
            start = s;
            end = e;
        }
    }
}
